Матч 334, Расширенное счастливое число

(ExtendedHappyNumbers)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 2

Дано натуральное число n. Возведем в k - ую степень каждую его цифру и просуммируем полученные результаты. Обозначим результат через S_k(n). Например, S₂(65) = 6² + 5² = 61. Построим последовательность n, S_k(n), S_k(S_k(n)), … . Счастьем числа n по отношению к k будем называть наименьшее число в этой последовательности.

По заданным числам a, b и k следует найти счастье каждого числа между a и b включительно по отношению к k и вернуть их сумму.

Класс: ExtendedHappyNumbers

Метод: long long calcTheSum(int a, int b, int k)

Ограничения: 1 £ a, b £ 10⁶, 1 £ k £ 6.

Вход. Три числа a, b, k.

Выход. Найти счастье каждого числа между a и b включительно по отношению к k и вернуть их сумму.

Пример входа

a	b	k
13	13	2
1	5	2
535	538	3

Пример выхода

1

14

820

РЕШЕНИЕ

динамическое программирование

Поскольку значение k в процессе вычислений фиксировано, заведем массив powk, в котором powk[i] = i^k. Им будет удобно пользоваться при вычислении значений S_k(n) в функции sum(n). Наибольшее значение, которое могут принимать элементы последовательности n, S_k(n), S_k(S_k(n)), …, не больше 4*10⁶, так как даже при k = 6 значение S₆(n) при n < 4*10⁶ не больше 3⁶ + 6*9⁶ = 3189375 < 4*10⁶.

Заведем массив f[4000000], в котором будем хранить f[i] = S_k(i). Рассмотрим для некоторого i последовательность a₀ = i, a₁ = S_k(i), a₂ = S_k(S_k(n)), … . Очевидно, что найдутся такие индексы s и t (пусть s < t для определенности), что a_s = a_t. Тогда f[a_k], (0 £ k £ t) положим равным минимуму среди чисел a_k, a_k+1, …, a_t. При этом начиная вычислять значение f[a₀], в процессе мы находим все значения f[a_k], 0 £ k £ t.

Описанную процедуру совершаем в функции g. Значение f[i] считается вычисленным, если f[i] > 0. При первом проходе по числам a₀, …, a_t устанавливаем f[a_i] = -1. Дойдя до a_t = a_s, продолжаем путь a_s , a_s+1, …, a_t, устанавливая f[a_i] = a_i для s £ i £ t. Когда вторично дойдем до f[a_t], значение этой ячейки уже будет положительным и рекурсия начнет раскручиваться назад. Двигаясь назад по кольцу дважды от a_t до a_s, а потом и до a₀, устанавливаем f[a_i] в наименьшее значение среди чисел a_i, a_i+1, …, a_t.

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#define MAX 5000001

using namespace std;

int powk[10], f[MAX], ptr;

int sum(int n)

{

int s;

for(s = 0; n; n /= 10)

s += powk[n % 10];

return s;

}

int g(int n)

{

if (f[n] > 0) return f[n]; else

if (f[n] == 0) f[n] = -1; else

if (f[n] == -1) f[n] = n;

return f[n] = min(n,g(sum(n)));

}

class ExtendedHappyNumbers

{

public:

long long calcTheSum(int a, int b, int k)

{

int i, j, s;

long long res = 0;

for(i = 0; i < 10; i++)

{

for(s = 1, j = 0; j < k; j++) s *= i;

powk[i] = s;

}

for(i = a; i <= b; i++)

res += g(i);

return res;

}

};